#include "GA.h"
#include <random>


GA::GA(size_t size, size_t n, double crossover, double mutation, size_t iter) {
    this->size = size;
    this->POC = crossover;
    this->POM = mutation;
    this->iter = iter;
    // 初始化种群
    populations.resize(size);
    std::random_device rd;
    std::mt19937 gen(rd()); // 生成随机数
    for (int i = 0; i < size; ++i) {
        populations[i].resize(n);
        for (int j = 0; j < n; ++j) {
            populations[i][j] = j;
        }
        // 随机序列
        std::shuffle(populations[i].begin(), populations[i].end(), gen);
    }
    // 初始化最优解
    best = populations[0];
}

void GA::run(Job &job) {
    for (int i = 0; i < iter; ++i) {
        // 选择父代种群
        selectParent(job);
        // 交叉生成子代种群
        crossover();
        // 突变子代种群
        mutation();
        // 重新选择当前种群
        select(job);
        // 记录最优解
        for (auto& rank: populations) {
            if (job.makespan(best) > job.makespan(rank)) {
                best = rank;
            }
        }
    }
    job.setRank(best);
}

void GA::selectParent(Job& job) {
    long double sum = 0;
    // 求目标函数之和
    for (const auto& rank: populations) {
        sum += job.makespan(rank);
    }
    // 生成0到1的随机数
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_real_distribution<double> dis(0, 1);
    // 生成父代种群
    for (const auto& rank: populations) {
        if (dis(gen) <= 1 - job.makespan(rank) / sum) {
            parents.push_back(rank);
        }
    }
}

void GA::crossover() {
    std::random_device rd;
    std::mt19937 gen(rd());
    // 选择两个序列作为父序列和母序列
    for (auto &fatherRank : parents) {
        for (auto &motherRank: parents) {
            // 不能自己和自己进行基因交叉
            std::uniform_real_distribution<double> dis1(0, 1);
            if (dis1(gen) <= POC && fatherRank != motherRank) {
                size_t n = fatherRank.size();
                std::vector<int> childrenRank(n, -1);
                // 随机生成两个整数用于截取父序列的片段
                std::uniform_int_distribution<int> dis2(0, int(n) - 1);
                int begin = 0, end = 0;
                while (begin >= end) {
                    begin = dis2(gen), end = dis2(gen);
                }
                // 截取父序列
                for (int i = begin; i <= end; ++i) {
                    childrenRank[i] = fatherRank[i];
                }
                // 从截取的片段右边开始，依次将母序列的值进行记录
                int i = end + 1, j = end + 1;
                while (true) {
                    // 防止溢出
                    if (i == n) {
                        i = 0;
                    }
                    if (j == n) {
                        j = 0;
                    }
                    // 标记，当新序列生成好后，跳出循环
                    bool flag = true;
                    for (auto rank: childrenRank) {
                        if (rank == -1) {
                            flag = false;
                        }
                    }
                    if (flag) {
                        break;
                    }
                    // 如果当前位置的值以及被记录就跳过
                    while (std::find(childrenRank.begin(), childrenRank.end(), motherRank[j]) != childrenRank.end()) {
                        ++j;
                        if (j == n) {
                            j = 0;
                        }
                    }
                    childrenRank[i] = motherRank[j];
                    ++i, ++j;
                }
                // 记录新序列
                children.push_back(childrenRank);
            }
        }
    }
}

void GA::mutation() {
    std::vector<std::vector<int>> newPopulation;
    for (auto &rank : children) {
        // 生成一个0到1的随机数作为突变概率
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_real_distribution<double> dis1(0, 1);
        double p = dis1(gen);
        // 根据概率进行突变
        if (p < POM) {
            std::uniform_int_distribution<int> dis2(0, int(rank.size()) - 1);
            int j = 0, k = 0;
            // 随机挑选两个位置进行插入
            while (j == k) {
                j = dis2(gen), k = dis2(gen);
            }
            // 复制原序列，将k位置插入到j位置之后
            size_t n = rank.size();
            std::vector<int> newRank(n);
            int index1 = 0, index2 = 0;
            while (index1 != n && index2 != n) {
                if (index2 != j && index2 != k) {
                    newRank[index1++] = rank[index2++];
                }
                else if (index2 != k) {
                    newRank[index1++] = rank[index2++];
                    newRank[index1++] = rank[k];
                }
                else {
                    ++index2;
                }
            }
            // 记录新序列
            newPopulation.push_back(newRank);
        }
    }
    // 将得到的所有新序列归入种群中
    children.insert(children.end(), newPopulation.begin(), newPopulation.end());
}

void GA::select(Job& job) {
    populations.insert(populations.end(), children.begin(), children.end());
    // 排序，截取最好的子序列
    std::sort(populations.begin(), populations.end(),[&](auto a, auto b) {
        return job.makespan(a) < job.makespan(b);
    });
    populations.resize(size);
    parents.clear();
    children.clear();
}